/*
 * Поиск в тексте
 *
 * suffix tree
 */

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/* #define MEMDEBUG */

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif
#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))
#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))
#define MIN(a, b)	((a) < (b) ? (a) : (b))

static int _alloc_count = 0;

/* queue */
struct queue {
	char *data;
	size_t _data_size;

	int head;
	int n;
	int _max;
};

/* stack */
struct stack {
	char *data;
	size_t n; /* how many elements in the stack atm */
	size_t _data_size; /* size of one element (in bytes) */
	size_t _allocated; /* how much storage is allocated for *data (in bytes) */
	size_t _max; /* maximum storage that we are allowed allocate for *data */
};

/* autoarray */
struct vector {
	char *data;
	size_t _elem_size;

	int n;
	int _max;
};

/* doubly-linked list */
struct dll_node {
	int x, y;
	char *data;
	size_t _data_size;
	struct dll_node *prev, *next;
};

/* suffix tree */
struct suftree {
	char *string;
	size_t string_len;
	struct suftree_edge *edges[26 + 1];

	int suffix; /* start of string match range for this node */
	int id; /* suffix ID ? */
	bool root, final;
};

struct suftree_edge {
	/* struct suftree_node *next; */
	struct suftree *node;
	int lo, hi; /* XXX */
};

/* {{{ function prototypes */
/* memory allocation wrappers */
char *s_calloc(size_t n, size_t size);
char *s_malloc(size_t size);
char *s_realloc(char *oldptr, size_t newsize);

struct queue *queue__new(const int n, const size_t elem_size);
int queue__push(struct queue *q, const void *p);
int queue__pop(struct queue *q, void *buf);
int queue__cleanup(struct queue *q);

struct vector *vector__new(size_t elem_size, int p);
int vector__append(struct vector *v, const void *app);
char *vector__get_by_idx(struct vector *v, const int idx);
int vector__cleanup(struct vector *v);

struct dll_node *dll_insert(struct dll_node *node, struct dll_node *ins);
struct dll_node *dll_delete(struct dll_node *node);
void dll_mergesort(struct dll_node *head, int (*cmp)(const void *, const void *));

/* }}} */

/* {{{ memory allocation wrappers */
extern char *
s_calloc(size_t n, size_t size)
{
	void *ptr;
	ptr = calloc(n, size);
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): calloc %lu times %lu bytes (tot %.4f MiB)\t%p\n",
			__func__, n, size, ((float) n * size) / (1024.0f * 1024.0f), ptr);
#endif /* MEMDEBUG */
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	_alloc_count++;
	return ptr;
}

extern char *
s_malloc(size_t size)
{
	void *ptr;
	ptr = malloc(size);
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): malloc %lu bytes (%.4f MiB)\t\t%p\n",
			__func__, size, (float) size / (1024.0f * 1024.0f), ptr);
#endif /* MEMDEBUG */
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	_alloc_count++;
	return ptr;
}

extern char *
s_realloc(char *oldptr, size_t newsize)
{
	void *newptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): realloc oldptr %p for new size of %lu (%.4f MiB)\n",
			__func__, oldptr, newsize, (float) newsize / (1024.0f * 1024.0f));
#endif
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): newptr %p\n", __func__, newptr);
#endif /* MEMDEBUG */
	return newptr;
}

void
s_free(void *ptr)
{
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): freeing %p\n", __func__, ptr);
#endif /* MEMDEBUG */
	if (ptr)
		_alloc_count--;
	free(ptr);
}
/* }}} */

/* {{{ queue */
extern struct queue *
queue__new(const int n, const size_t elem_size)
{
	struct queue *q = NULL;

	assert(n >= 1);
	assert(elem_size > 0);

	q = (struct queue *) s_malloc(sizeof *q);
	q->data = (char *) s_calloc(n, elem_size);
	q->_data_size = elem_size;
	q->head = 0;
	q->n = 0;
	q->_max = n;

	return q;
}

extern int
queue__push(struct queue *q, const void *p)
{
	assert(q != NULL);
	assert(p != NULL);

	if (q->n >= q->_max) {
		#ifdef QUEUE_DEBUG
		fprintf(stderr, "%s(): q->n (%d) >= q->_max (%d), can't push any deeper :-(\n",
				__func__, q->n, q->_max);
		#endif /* QUEUE_DEBUG */
		return -1;
	}

	memcpy(q->data + ((q->head + q->n++) % q->_max) * q->_data_size, p, q->_data_size);
	#ifdef QUEUE_DEBUG
	fprintf(stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n);
	#endif /* QUEUE_DEBUG */

	return 0;
}

extern int
queue__pop(struct queue *q, void *buf)
{
	assert(q != NULL);
	assert(buf != NULL);

	memcpy(buf, q->data + (q->head) * q->_data_size, q->_data_size);
	q->head = (q->head + 1) % q->_max;
	q->n--;
	#ifdef QUEUE_BEBUG
	fprintf(stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n);
	#endif /* QUEUE_DEBUG */

	return 0;
}

extern int
queue__cleanup(struct queue *q)
{
	S_assert(q != NULL);
	if (q == NULL)
		return -1;

	if (q->_max == 0 || q->data == NULL)
		return 1;

	s_free(q->data);
	q->data = NULL;
	s_free(q);

	return 0;
}
/* }}} */

/* {{{ autoarray */
extern struct vector *
vector__new(size_t elem_size, int p)
{
	struct vector *v = NULL;

	if (p < 0)
		p = 0;

	v = (struct vector *) s_malloc(sizeof *v);
	v->_max = 1 << p;
	v->_elem_size = elem_size;
	v->n = 0;
	v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);

	return v;
}

extern int
vector__append(struct vector *v, const void *app)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max == 0) {
		/* weird input, fix it */
		ret |= 2;
		debug_fprintf((stderr, "%s(): v->_max is 0, which means that your "
					"autoarray (v=%p) is messed up. trying to fix this.\n",
					__func__, (void*) v));
		if (v->_elem_size == 0) {
			ret |= 4;
			fprintf(stderr, "%s(): can't fix this mess, bailing out (%d)\n",
					__func__, ret);
			return ret;
		} else {
			v->_max = 1;
			v->n = 0;
			v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);
		}
	}

	if (v->n + 1 >= v->_max) {
		v->data = (char *) s_realloc(v->data, v->_elem_size * (v->_max *= 2));
	}
	memcpy(v->data + (v->n++) * v->_elem_size, app, v->_elem_size);

	return ret;
}

extern char *
vector__get_by_idx(struct vector *v, const int idx)
{
	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (NULL)\n",
				__func__);
		return NULL;
	}

	if (v->_elem_size == 0) {
		fprintf(stderr, "%s(): whoah, looks like your vector is messed up big time (NULL)\n",
				__func__);
		return NULL;
	}

	if (idx < 0 || idx >= v->n) {
		fprintf(stderr, "%s(): index out of range %d (v->n=%d)\n",
				__func__, idx, v->n);
		return NULL;
	}

	return v->data + (idx) * v->_elem_size;
}

extern int
vector__cleanup(struct vector *v)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max > 0) {
		v->_max = v->n = 0;
		s_free(v->data);
		v->data = NULL;
	} else {
		ret |= 1;
	}

	/* TODO: improve logic */
	debug_fprintf((stderr, "%s(): freeing v=%p\n", __func__, (void*) v));
	s_free(v);

	return ret;
}
/* }}} */

/* {{{ doubly-linked list */
/*
 * This function inserts one node pointed to by 'ins' _after_ 'node'.
 */
extern struct dll_node *
dll_insert(struct dll_node *node, struct dll_node *ins)
{
	assert(node != NULL);
	if (ins == NULL) {
		debug_fprintf((stderr, "dll_insert(): ins is NULL, not doing anything\n"));
		return node;
	}

	if (node->next) {
		assert(node->next->prev == node);
		node->next->prev = ins;
	}
	ins->next = node->next;
	ins->prev = node;
	node->next = ins;
	return ins;
}

/*
 * This function extracts 'node' from a doubly-linked list and returns pointer
 * to that node, pointers '->prev' and '->next' are not reset.
 *
 * If you really want to get rid of a node, call
 * 	free(dll_delete(unneeded_node));
 */
extern struct dll_node *
dll_delete(struct dll_node *node)
{
	if (!node) {
		debug_fprintf((stderr, "dll_delete(): received NULL ptr, wtf am i supposed to delete?\n"));
		return NULL;
	}

	if (node->prev) {
		assert(node->prev->next == node);
		node->prev->next = node->next;
	}
	if (node->next) {
		assert(node->next->prev == node);
		node->next->prev = node->prev;
	}

	return node;
}

/*
 * Merge-sort for doubly-linked list.
 *
 * TODO: work out the use of (*cmp)() function
 */
extern void
dll_mergesort(struct dll_node *head, int (*cmp)(const void *, const void *))
{
	struct dll_node *end, *mid;
	struct dll_node *sorted, *first, *second;
	struct dll_node *swap;

	if (head == NULL || head->next == NULL) /* lengths 0, 1 */
		return;

	end = mid = head;
	while (end && end->next && end->next->next) {
		end = end->next->next;
		mid = mid->next;
	}
	if (end && end->next) {
		end = end->next;
		mid = mid->next;
	}

	mid->prev->next = NULL;
	mid->prev = NULL;
	dll_mergesort(head, cmp);
	dll_mergesort(mid, cmp);

	if (cmp(head->data, mid->data) > 0) { /* this is the tricky part */
		char *t1;
		size_t t2;
		struct dll_node *t3;
		int t4;
#define SWAP_(a,b,t) do{(t)=(a),(a)=(b),(b)=(t);}while(0)
		if (head->next && mid->next)
			SWAP_(head->next->prev, mid->next->prev, t3);
		SWAP_(head->x, mid->x, t4);
		SWAP_(head->data, mid->data, t1);
		SWAP_(head->_data_size, mid->_data_size, t2);
		SWAP_(head->prev, mid->prev, t3);
		SWAP_(head->next, mid->next, t3);
#undef SWAP_
	}

	/*
	 * from now on using only ->prev and ->next pointers should suffice us
	 */
	first = head->next;
	if (first) first->prev = NULL;
	second = mid;

	sorted = head;
	sorted->next = NULL;
	assert(sorted->prev == NULL);

	while (first && second) {
		assert(sorted->next == NULL);

		/* TODO: un-copypaste this code (use 'swap' ptr) */
		if (cmp(first->data, second->data) < 0)
			swap = first;
		else
			swap = second;

		assert(swap->prev == NULL);

		sorted->next = swap;
		swap->prev = sorted;
		sorted = swap;

		swap = swap->next;
		if (swap) {
			assert(swap->prev == sorted);
			swap->prev->next = NULL;
			swap->prev = NULL;
		}
	}
	assert(sorted->next == NULL);
	if (first) {
		assert(first->prev == NULL);
		sorted->next = first;
		first->prev = sorted;
	}
	if (second) {
		assert(second->prev == NULL);
		sorted->next = second;
		second->prev = sorted;
	}
}
/* }}} */

/* {{{ suffix tree */
/*
 * This one is a little messy.
 * Careless Programming Style.
 */
int
suftree__add_suffix(struct suftree *root, int shift, const int suffix)
{
	struct suftree_edge *E;
	int idx = root->string[shift] != '\n' ? root->string[shift] - 'a' : 'z' - 'a' + 1;

	assert(root->string);
	assert(root->string_len >= 1);

	if (root->string[suffix] == '\n')
		return 1;

	E = root->edges[idx];

	if (E != NULL) {
		/* found an existing edge => at least first chars match */
		int match_len = 1;
		while (root->string[shift + match_len] == root->string[E->lo + match_len] && 
				root->string[shift + match_len] &&
				root->string[E->lo + match_len] &&
				E->lo + match_len < E->hi) {
			match_len++;
		}

		if (match_len < E->hi - E->lo) {
			/* split the edge */
			struct suftree *M = s_calloc(1UL, sizeof *M);
			struct suftree_edge *R = s_calloc(1ul, sizeof *R);
			/* struct suftree_edge *N = s_calloc(1ul, sizeof *N); */

			/*
			 * Strike this. It works only for a particular case.
			 * WAIT! This work every time, because if we're here,
			 * then it means that we've found different chars and
			 * different char are, you know, different. This IS general
			 * case code. Oh well, too late now. One level of recursion
			 * more, nobody will notice. I guess, we'll save up on code
			 * size!

			 * create a 'remainder' edge * 
			R->lo = E->lo + match_len;
			R->hi = E->hi;
			R->node = E->node;

			 * update the current edge * 
			E->hi = E->lo + match_len;
			E->node = M;

			 * insert a mid-way node (connected to the current edge) * 
			M->string = root->string;
			M->string_len = root->string_len;
			M->edges[root->string[R->lo] - 'a'] = R;

			 * append a new edge to the mid-way node * 
			N->lo = shift + match_len;
			N->hi = root->string_len;
			M->edges[root->string[shift + match_len] - 'a'] = N;
			 */

			R->lo = E->lo + match_len;
			R->hi = E->hi;
			R->node = E->node;

			E->hi = R->lo; /* E->hi = E->lo + match_len; */
			E->node = M;

			M->string = root->string;
			M->string_len = root->string_len;
			M->suffix = -1;

			idx = root->string[R->lo] != '\n' ? root->string[R->lo] - 'a' : 'z' - 'a' + 1;
			M->edges[idx] = R;

			return suftree__add_suffix(M, shift + match_len, suffix);
		} else if (match_len == E->hi - E->lo) {
			/* full match up until the end of the edge */
			return suftree__add_suffix(E->node, shift + match_len, suffix);
		} else {
			/* Woah! Unbelieavable! */
			fprintf(stderr, "%s():%d: Unexpected error. root->string=\"%*s\" shift+match_len=%d\n", __func__, __LINE__,
					(int) root->string_len - 1, root->string, shift + match_len);
		}
	} else {
		/* create a new edge */
		E = root->edges[idx] = s_calloc(1UL, sizeof *root->edges[0]);

		E->lo = shift;
		E->hi = root->string_len;

		E->node = s_calloc(1UL, sizeof *E->node);
		E->node->string = root->string;
		E->node->string_len = root->string_len;
		E->node->suffix = suffix;
		E->node->final = true;
	}
	return 0;
}

struct suftree *
suftree__new(char *text)
{
	struct suftree *root;
	int i = 0;

	root = s_calloc(1UL, sizeof *root);
	/* root->string = s_malloc(strlen(text));
	 * memcpy(root->string, text, strlen(text)); */
	root->string = text;
	root->string_len = strlen(text);
	root->root = true;
	root->suffix = -2;
	S_assert(root->string[root->string_len - 1] == '\n');

	while (i < root->string_len) {
		/* add every suffix of 'text' */
		suftree__add_suffix(root, i, i);
		i++;
	}

	return root;
}

int
suftree__contains(struct suftree *root, const char *p)
{
	register int i = 0;
	struct suftree_edge *edge = root->edges[p[i] - 'a'];
	int diff = edge ? edge->lo : -1;

	while (p[i] && edge) {
		S_assert(root != NULL);
		S_assert(edge->node != NULL);
		S_assert(diff != -1);

		while (i + diff < edge->hi && p[i] && p[i] == root->string[i + diff])
			i++;

		if (i + diff < edge->hi && p[i] && p[i] != root->string[i + diff]) {
			goto negative;
		} else if (!p[i]) {
			goto affirmative;
		} else if (i + diff == edge->hi) {
			root = edge->node;
			edge = root->edges[p[i] - 'a'];
			diff = edge ? edge->lo - i : -1;
		} else {
			fprintf(stderr,
					"%s():%d: Unexpected error.\n"
					"%s():%d: p = \"%s\", p + i = \"%s\", "
					"i = %d, diff = %d, edge->lo = %d, "
					"edge->hi = %d\n",
					__func__, __LINE__, __func__, __LINE__,
					p, p + i, i, diff, edge->lo, edge->hi);
		}
	}
	if (!edge && p[i])
		goto negative;

affirmative:
	return (!(0));
negative:
	return 0;
}

int
suftree__cleanup(struct suftree *root)
{
	int i;
	for (i = 0; i < sizeof root->edges / sizeof root->edges[0]; i++) {
		if (root->edges[i]) {
			suftree__cleanup(root->edges[i]->node);
			s_free(root->edges[i]);
		}
	}
	s_free(root);

	return 0;
}
/* }}} */

int
main(int argc, char **argv)
{
	char *text, *patt, *lf;
	int n, i;
	struct suftree *st;

	text = s_calloc(5003UL, sizeof *text);
	fgets(text, 5002, stdin);
	if (lf = strrchr(text, '\n'), lf == NULL) {
		text[strlen(text) + 1] = '\0';
		text[strlen(text)] = '\n';
	}
	st = suftree__new(text);

	patt = s_malloc(1000003UL);
	fgets(patt, 1000002, stdin);
	sscanf(patt, "%d", &n);
	for (i = 0; i < n; i++) {
		fgets(patt, 1000001, stdin);
		if (lf = strrchr(patt, '\n'), lf) *lf = '\0';
		if (suftree__contains(st, patt))
			puts(patt);
	}

	suftree__cleanup(st);
	s_free(patt);
	s_free(text);
	(void) fprintf(stderr, "_alloc_count = %d\n", _alloc_count);
	return 0;
}
